1. Field of the Invention
This invention relates to data processing systems and more specifically to a method and apparatus for resolving the allocation of a shared resource on a priority basis such that the requester having the lowest priority has the shortest path through the priority resolving logic.
2. Description of the Prior Art
FIG. 1 shows a data processing system comprised of a CPU 101, a main memory 102, a first I/O controller 103 with an attached I/O device 105 and a second I/O controller 104 with an attached I/O device 106, and common bus 107. In FIG. 1, the thinner lines connecting the various components are control lines and the thicker lines connecting the components are data/address lines. In this system, both program instructions and data are stored in main memory 102.
Main memory 102 is a dual ported memory such that one port connects to the common bus 107 so that memory requests and data transfers may be made by either I/O controller 103 or I/O controller 104 via common bus 107 whereas requests for memory from CPU 101 normally take place directly between CPU 101 and main memory 102 without going via common bus 107.
Because main memory 102 maintains information in volatile RAM array 110, such as MOS semiconductor memory chips, it requires periodic refresh in order not to lose its information content. Main memory 102 contains refresh logic 109 which periodically makes a request for the memory for the purpose of refreshing the volatile RAM array 110.
Priority resolver logic 108 is provided within the main memory 102 to resolve the possible conflicts between competing requests for access to RAM array 110. These competing requests can come from an I/O controller wanting access to the main memory to read or write information from it or into it or from the CPU requesting to read or write into RAM array 110 or from refresh logic 109 requesting access to the RAM array in order to refresh the information contained therein. Priority resolver 108 is in addition to any priority scheme which is used to resolve competing requests for use of the common bus.
In a system in which the refresh logic 109, I/O controller 103 or 104 and CPU 101 may be making competing requests, it is well known in the art to assign priorities to the competing requests such that the highest priority requester will be granted the shared resource over any lower priority requesters then making a request. One scheme is to assign the highest priority to the refresh logic, the medium priority to a request from the common bus which in this case would be from another one of the I/O controllers 103 or 104 and the lowest priority of the CPU 101.
This assignment of priority levels has the advantage that the refresh logic normally must receive access at well defined periodic intervals in order to refresh volatile RAM array 110 and the postponement of the refreshing can result in loss of memory information. Middle priority is assigned to requests originating from the common bus, which in this case in from the I/O controllers, because I/O controllers are usually in less of a position to be postponed too long when requesting access to the main memory. For instance, when writing to a disk, if the data is not immediately avalible to the disk and arrives too late to the controller, the disk will have rotated further than the desired position to write the data and this will result in a data underrun error. When reading from a disk, if the data is not taken from the I/O controller, the second word of data may arrive before the first word is taken and result in a data overrun error. Because the time constraints in reading and writing to an I/O device are usually such that a refresh operation can be performed between successive words of data, the refresh operation is given higher priority over that of access from the common bus. Memory requests from the CPU are given the lowest priority because the CPU is usually designed such that access to operand data and program instructions within the main memory is not critical to the extent that the CPU can wait until the memory becomes available without losing data. The only consequence of having to wait being that the program executes more slowly each time the CPU has to wait for the memory to become available to it. Thus, access priority is assigned in the order of real time constraints with the device having the least demanding time constraint being given the lowest priority.
Although various schemes from resolving competing requests on a priority basis are well known in the art, most of these schemes work such that the shared resources is granted to the highest priority device in the shortest amount of time, that is, the priority resolver has the shortest logical path used by the highest priority request. Alternatively, the logic paths for all requests are of equal length such that the resolution of the competing requests takes equal time, independent of the priority level of the requester. However, because the central processing unit in most data processing systems makes the most requests of main memory and it is often assigned the lowest priority with respect to access of the main memory, it would be desirable in order to speed up program execution wherever possible to have the lowest priority requester have the shortest logical path through the resolver logic.
Further, most priority resolvers allocate the shared resource on a fixed priority basis. However, there may be times when the priority assignment must be changed. For example, if the CPU which normally does not access memory while performing a real time operation performs an operation that has real time constraints, such as a very high speed transfer to disk or a communication line, where the data flows through the CPU on its way to or from memory. In this case, the CPU priority level must be raised so the CPU will have priority over other I/O requests during the high speed transfer.
Therefore, what is desired is to have a priority resolver logic with the shortest logical path being used by the lowest priority requesting device. It is also desirable in a priority resolver, particularly when resolving competing requests for access to main memory, to be able to initiate a cycle as early as possible even before the final resolution as to which one of the competing requests will be granted access to the shared resource. Further, it is desirable to be able to dynamically raise in priority level one or more low priority levels so that they are given higher priority as conditions require.